#include <bits/stdc++.h>

using namespace std;

// 环形子数组的最大和
// 给定一个数组nums，长度为n
// 假设下标0和下标n-1是连接在一起的
// nums是一个环形数组
// 返回环形数组中子数组的最大累加和
// 测试链接 : https://leetcode.cn/problems/maximum-sum-circular-subarray/

class Solution 
{
public:
    // 动态规划
    int maxSubarraySumCircular1(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n);
        auto g = f;

        int fmax = nums[0], gmin = nums[0], sum = nums[0];
        f[0] = nums[0], g[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            int x = nums[i];
            sum += x; // 整个数组的和
            f[i] = max(x, x + f[i - 1]); // 以 nums[i] 结尾的最大子数组和
            fmax = max(fmax, f[i]); // 最大大数组和
            g[i] = min(x, x + g[i - 1]); // 以 nums[i] 结尾的最小子数组和
            gmin = min(gmin, g[i]); // 最小子数组和
        }
        // 判断整个数组是不是全负数
        return gmin == sum ? fmax : max(fmax, sum - gmin); 
    }

    // 空间压缩
    int maxSubarraySumCircular2(vector<int>& nums) 
    {
        int n = nums.size(), maxsum = nums[0], minsum = nums[0], all = nums[0];
        for(int i = 1, maxpre = nums[0], minpre = nums[0]; i < n; ++i)
        {
            all += nums[i]; // 整个数组的和
            maxpre = max(nums[i], nums[i] + maxpre); // 以 nums[i] 结尾的最大子数组和
            maxsum = max(maxsum, maxpre); // 最大子数组和
            minpre = min(nums[i], nums[i] + minpre); // 以 nums[i] 结尾的最小子数组和
            minsum = min(minsum, minpre); // 整个数组的最小子数组和
        }
        // 判断整个数组是不是全负数
        return all == minsum ? maxsum : max(maxsum, all - minsum); 
    }
};